This invention relates to a switching device, and in particular to an ATM switching device which exhibits fairness in the way in which it handles incoming traffic at different inputs.
One proposed solution to the problem of allocating network resources to the users of an integrated services network for packet-based traffic is known as Weighted Fair Queuing, in which arriving data packets are reordered so that they are retransmitted with a degree of fairness in the processor sharing system. See, for example, Parekh and Gallagher xe2x80x9cA Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Casexe2x80x9d IEEE/ACM Transactions on Networking, Vol. 1, No. 3, June 1993. Such a system, however, can be very complex to implement.
U.S. Pat. No. 5,455,825 discloses a switch for digital communications networks, including a queuing system. When incoming cells or packets arrive, they are provided with numerical tags, calculated in accordance with a desired scheduling algorithm, and placed in a queue. A queue and search module, designed for VLSI implementation, selects the cells or packets for transmission based on the tags. Thus, the queue is searched, and, for each destination, the cell with the smallest tag value is sent for transmission. Such searching can, however, be time-consuming.
The present invention seeks to provide a switching device which provides fair queuing between its different input connections. In one aspect, this is achieved by storing received input data in a memory, together with an associated pointer, the pointer being indicative of a priority which is to be given to transmission of the data. The pointers are accessed through an array, which groups together the calls which have the same transmission, avoiding the need for lengthy searching. In another aspect, fair queuing is provided until the number of cells from a single input connection, awaiting transmission, exceeds a threshold number. Further cells from that input connection are then treated in a non-fair way.